{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Parcours de Graphes\n", "\n", "L'idée derrière le parcours de graphe est de trouver des chemins entre des sommets.\n", "En fonction du but de la recherche de chemin, différents algorithmes sont utilisés.\n", "\n", "Par exemple, pour trouver le plus court chemin entre deux sommets d'un graphe, on fera souvent un parcours en largeur du graphe.\n", "\n", "Le but de ce TP est d'explorer plusieurs façons de trouver des chemins dans un graphe, en voyant comment trouver un chemin optimal dans un graphe, puis dans un graphe pondéré et enfin, comment on peut essayer d'améliorer l'exécution de notre algorithme.\n", "\n", "**Ce TP est à rendre pour vendredi 5 février avant le cours. (On fera la correction au début du prochain cours.)**" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Structures de Données\n", "\n", "Pour effectuer un parcours en largeur efficace, on a besoin d'une structure de données particulière : une file.\n", "\n", "Une file est une liste d'éléments qui permet :\n", "\n", "* de rajouter des éléments à la fin en temps constant ;\n", "* de récupérer le premier élément en temps constant.\n", "\n", "On appelle ça une méthode FIFO, pour \"First In, First Out\", ou PEPS en français (\"Premier Entré, Premier Sorti\").\n", "C'est donc adapté au parcours en largeur : on rajoute les sommets du graphe dans l'ordre où on les rencontre, puis on les visite dans cet ordre là également.\n", "\n", "En `Python`, on peut utiliser l'objet `deque` (pour \"double-ended queue).\n", "Voilà quelques exemples d'ajout et de retrait d'éléments dans un `deque` :" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from collections import deque" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# initialisation d'un deque\n", "d = deque([1,2,3])\n", "print(\"Valeur initiale :\", d, \"\\n\")\n", "\n", "# ajout d'un élément à la fin \n", "d.append(4)\n", "print(\"Valeur après ajout du 4 :\", d, \"\\n\")\n", "\n", "# retrait du premier élément\n", "a = d.popleft()\n", "print(\"Élément retiré :\", a)\n", "print(\"Nouvelle valeur de deque :\", d)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** Dans une file, on n'a accès qu'aux fonctions `append` pour rajouter un élément à la fin, et `popleft` pour enlever un élément du début. Pour compter le nombre d'éléments dans une file, on doit donc enlever tous les éléments un par un, jusqu'à ce que la file soit vide.\n", "\n", "Remarque : si `d` est un `deque`, `if d` est vrai si `d` n'est pas vide, on peut donc itérer sur `d` tant qu'il n'est pas vide avec `while d`." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def longueur(d):\n", " # implémenter la fonction" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "scrolled": true }, "outputs": [], "source": [ "# pour tester la fonction\n", "d = deque([1,2,3,4])\n", "longueur(d)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Parcours en Largeur\n", "\n", "Maintenant qu'on sait comment faire une file, on est prêt-es pour parcourir un graphe en largeur.\n", "\n", "On va utiliser la représentation des graphes par liste d'adjacence.\n", "Pour cela, vous pouvez utiliser la fonction suivante, qui prend un graphe en entrée et qui renvoit les listes d'adjacence correspondantes :" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import networkx as nx\n", "import numpy as np\n", "import matplotlib.pyplot as plt" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def liste_adjacence(G):\n", " adj = {}\n", " \n", " for sommet, adjacence in G.adjacency():\n", " adj[sommet] = adjacence.keys()\n", " \n", " return adj" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** Voilà un graphe aléatoire, afficher le graphe et sa liste d'adjacence. Observez." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "G_aleatoire = nx.fast_gnp_random_graph(4, 0.4, seed=123)\n", "\n", "# afficher la liste d'adjacence du graphe et le graphe, " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On va avoir besoin d'afficher des graphes, pour cela, vous pouvez utiliser la fonction `afficher_graphe` suivante.\n", "Elle prend en argument un graphe `G` et un dictionnaire de couleurs, voilà un exemple de comment définir ce dictionnaire." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def afficher_graphe(G, couleurs=None):\n", " pos = nx.spring_layout(G, seed=42)\n", " \n", " if couleurs is None:\n", " couleurs = {s: \"white\" for s in G.nodes()}\n", " \n", " nx.draw(G, \n", " pos,\n", " node_color=couleurs.values(), \n", " edgecolors=\"black\",\n", " with_labels=True,\n", " node_size=500)\n", " \n", " plt.show()" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# par exemple \n", "G_complet = nx.complete_graph(5)\n", "couleurs = {s: \"pink\" for s in G_complet.nodes()}\n", "afficher_graphe(G_complet, couleurs)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Comme on l'a vu en cours, le principe du parcours en largeur consiste à garder en mémoire :\n", "\n", "* une file `a_visiter` qui correspond aux éléments que l'on a repérés mais pas encore visités ;\n", "* une liste `visites` qui correspond aux éléments que l'on a déjà visités ;\n", "* un dictionnaire `predecesseur` qui indique, pour chaque sommet, quel sommet y a mené dans le parcours (cela va permettre de trouver le plus court chemin).\n", "\n", "On pourra initialiser le dictionnaire prédecesseur à `predecesseur = {s: None}`, de façon à savoir qu'on est tombé-es sur le sommet initial car c'est le seul à avoir `None` comme prédecesseur.\n", "\n", "Au début, `a_visiter` contient seulement le sommet duquel on part.\n", "L'algorithme procède alors ainsi :\n", "\n", "Tant que `a_visiter` n'est pas vide :\n", "* tirer `s` dans la file (premier élément de la file) ;\n", "* ajouter `s` à `visites` ;\n", "* pour chaque sommet voisin `v` de `s` (donc dans `adj(s)`) :\n", " * si `v` est dans `visites` (on l'a déjà traité) ou dans `a_visiter` (on a déjà prévu de le traiter), l'ignorer ;\n", " * sinon, le rajouter dans `a_visiter`, et définir `predecesseur[v] = s`." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** Implémentez l'algorithme de parcours en largeur décrit ci-dessus. \n", "\n", "On définira une fonction `parcours_largeur` qui prend en argument un graphe, un sommet initial, et un argument `afficher`.\n", "\n", "Si l'argument `afficher` vaut `True`, à chaque fois que vous explorez un nouvel sommet, vous afficherez le graphe avec, en couleur, les sommets que vous avez déjà explorés (pour cela, vous pouvez garder un dictionnaire `couleurs` que vous mettrez à jour au fur et à mesure)." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def parcours_largeur(G, sommet_initial, afficher=False):\n", " # implémentez l'algorithme dans cette fonction" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Essayez votre fonction avec la ligne suivante. Il faut que la fonction affiche l'état du graphe à chacune des étapes de l'exécution de l'algorithme, et renvoie le dictionnaire `predecesseur` dont il est question au dessus." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "scrolled": false }, "outputs": [], "source": [ "# tester la fonction sur un graphe\n", "predecesseur = parcours_largeur(nx.balanced_tree(3, 2), 1, afficher=True)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** Quelle est la complexité de cet algorithme ?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Chemin le Plus Court\n", "\n", "Dans la fonction `parcours_largeur`, vous avez implémenté le parcours en largeur d'un graphe.\n", "Au cours de ce parcours, on garde en mémoire un dictionnaire `predecesseur` tel que `predecesseur[v] = u` si le sommet `u` précède le sommet `v` dans le chemin entre le point de départ et `v`.\n", "\n", "Dès lors, on peut trouver le chemin entre `s` et `v`.\n", "En effet, `predecesseur[v]` contient l'avant dernier sommet du chemin entre `s` et `v`.\n", "De même, `predecesseur[predecesseur[v]]` renvoie l'avant-avant dernier sommet de ce chemin.\n", "\n", "En itérant jusqu'à tomber sur `s`, on a donc un chemin.\n", "\n", "Ce chemin est en fait le plus court chemin de `s` à `v`." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** Pourquoi (informellement) est-ce que le chemin obtenu de cette manière est un chemin le plus court entre `s` et `v` ?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** Implémenter une fonction `chemin(predecesseur, s, v)` qui, à partir du dictionnaire renvoyé par la fonction `parcours_largeur`, renvoie le chemin de `s` à `v`." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def chemin(predecesseur, s, v):\n", " # implémentez la fonction chemin ici" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Testez votre fonction avec le code suivant :" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "scrolled": false }, "outputs": [], "source": [ "# générer un graphe\n", "G = nx.connected_caveman_graph(4, 4)\n", "\n", "# calcul des prédécesseurs depuis le sommet 1\n", "predecesseurs = parcours_largeur(G, 1, afficher=False)\n", "\n", "# calculer le chemin entre les sommets 1 et 10\n", "chemin_court = chemin(predecesseurs, 1, 10)\n", "\n", "# afficher le chemin\n", "afficher_graphe(G, couleurs={s: \"pink\" if s in chemin_court else \"white\" for s in G.nodes()})" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** Rassembler la fonction `parcours_largeur` et la fonction `chemin` afin de définir une fonction `plus_court_chemin` qui prend en argument un graphe et deux sommets, et retourne le plus court chemin entre les deux dans le graphe.\n", "\n", "Vérifiez que vous retrouvez bien le chemin que vous obteniez à la question précédente." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def plus_court_chemin(G, s, v):\n", " # implémentez la fonction ici\n", " \n", "# pensez bien à vérifier que vous obtenez bien la même chose qu'à la question précédente !" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Labyrinthe\n", "\n", "On peut dès lors coder une fonction qui recherche un chemin dans un labyrinthe !\n", "\n", "Voilà une fonction qui génère un labyrinthe et une fonction qui l'affiche.\n", "Le labyrinthe est représenté en mémoire comme un graphe, où les sommets sont les cases du labyrinthe, et où il y a une arête entre deux sommets s'il est possible d'aller d'une case à une autre.\n", "\n", "On verra bientôt comment on peut utiliser des algorithmes de graphes pour générer des labyrinthes. :)\n", "\n", "\n", "La fonction `labyrinthe` renvoie un graphe qui correspond à la structure de labyrinthe décrite ci-dessus. Elle prend en argument la dimension du labyrinthe que l'on souhaite générer (par défaut 10 par 10 cases).\n", "\n", "La fonction `afficher_labyrinthe` permet d'afficher un labyrinthe, et l'on peut passer une liste de sommets (un chemin donc !) avec l'argument `solution` pour l'afficher." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from matplotlib.collections import LineCollection\n", "\n", "# generateur de labyrinthe\n", "def labyrinthe(dimension=(10, 10)):\n", " # générer une grille\n", " G = nx.grid_graph(dimension)\n", "\n", " # donner des poids aléatoires aux arêtes\n", " weights = {(u, v): np.random.random() for u in G.nodes() for v in G.nodes()}\n", " nx.set_edge_attributes(G, values=weights, name='weight')\n", "\n", " # calculer un arbre couvrant de poids maximal (on verra comment faire bientôt !)\n", " return nx.maximum_spanning_tree(G, algorithm=\"kruskal\")\n", "\n", "# affichage du labyrinthe\n", "def afficher_labyrinthe(lab, solution=None, explored=None):\n", " pos = {u: u for u in lab.nodes()}\n", " width, height = (1 + list(lab.nodes())[-1][0], 1 + list(lab.nodes())[-1][1]) \n", " \n", " plt.figure(figsize=(width, height))\n", " lines = [[(-0.5, -0.5), (width - 0.5, - 0.5)],\n", " [(-0.5, -0.5), (- 0.5, height - 0.5)],\n", " [(width - 0.5, -0.5), (width - 0.5, height - 0.5)],\n", " [(-0.5, height - 0.5), (width - 0.5, height - 0.5)]]\n", " \n", " for i in range(width):\n", " for j in range(height):\n", " if ((i, j), (i, j+1)) not in lab.edges():\n", " lines.append([(i - 0.5, j + 0.5), (i + 0.5, j + 0.5)])\n", " if ((i, j), (i+1, j)) not in lab.edges():\n", " lines.append([(i + 0.5, j - 0.5), (i + 0.5, j + 0.5)])\n", " \n", " if solution is not None:\n", " solx = [u for (u, v) in solution]\n", " soly = [v for (u, v) in solution]\n", " plt.plot(solx, soly, color=\"red\")\n", " \n", " if explored is not None:\n", " explx = [u for (u, v) in explored]\n", " exply = [v for (u, v) in explored]\n", " plt.scatter(explx, exply)\n", " \n", " plt.xlim(-0.5, width-0.5)\n", " plt.ylim(-0.5, height-0.5)\n", " plt.gca().add_collection(LineCollection(lines, colors=\"black\"))\n", " plt.axis(\"off\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On peut afficher un exemple de labyrinthe :" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "scrolled": false }, "outputs": [], "source": [ "lab = labyrinthe((10, 20))\n", "afficher_labyrinthe(lab)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** Utilisez la fonction de recherche de chemin que vous avez implémentée plus haut pour trouver un chemin dans ce labyrinthe. On partira de la case $(0, 0)$ pour arriver à la case opposée." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": { "scrolled": false }, "outputs": [], "source": [ "afficher_labyrinthe(lab, solution)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Un Algorithme plus Efficace\n", "\n", "Pour l'instant, notre algorithme de recherche de chemin parcourt tout le graphe pour trouver un chemin.\n", "\n", "Il n'est pas possible de trouver un meilleur algorithme, car dans le pire cas, on va devoir parcourir l'ensemble des sommets et des arêtes du graphe pour trouver une solution.\n", "\n", "En revanche, dans bien des cas, il y a vraiment beaucoup de chemins qui ne mènent à rien... par exemple, dans notre labyrinthe, à chaque branchement, un seul mène à la sortie, alors que les autres mènent à un cul de sac.\n", "\n", "On ne peut pas savoir a priori quel chemin est le bon, mais on peut se dire que, si le chemin nous fait revenir vers la gauche ou vers le bas, alors on a plus de chances de s'éloigner de la sortie.\n", "Ce type de raisonnement s'appelle un raisonnement **heuristique** : on sait que ce n'est pas toujours vrai, mais on se dit qu'on a plus de chances de trouver une solution en tournant dans une direction que l'on pense nous rapprocher de la sortie.\n", "\n", "C'est le principe de l'algorithme A*, qui est extrêmement utilisé dans les jeux vidéos, pour définir le déplacement des personnages autour d'obstacles : au lieu de tout chercher, on cherche en priorité les chemins qui devraient nous rapprocher." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Heuristique.** Comme heurisitque, on utilisera la distance à vol d'oiseau entre le sommet courant et le sommet que l'on cherche à rejoindre :" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def heuristique(s, v):\n", " return np.linalg.norm(np.array(s) - np.array(v))\n", "\n", "heuristique((0,0), (10,10))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Structure de données.** Dans l'algorithme de parcours en largeur étudié plus haut, on explorait le graphe, puis on décidait quel était le prochain sommet à visiter en prenant le sommet que l'on avait rencontré le plus tôt.\n", "On utilisait donc naturellement une structure de file : le premier élément exploré était le premier à être visité.\n", "\n", "Ici, au lieu de visiter les sommets dans l'ordre où on les rencontre, on visite le sommet que l'on pense être le plus proche de la sortie du labyrinthe.\n", "\n", "On va donc utiliser une **file de priorité**, qui garde en mémoire des tuples de la forme `(valeur, élément)`.\n", "Elle fonctionne ensuite comme une file classique, sauf qu'au lieu de renvoyer le premier élément qui y a été ajouté, elle renvoie l'élément dont la *valeur* est la plus faible.\n", "\n", "En Python, on peut utiliser l'objet `PriorityQueue`. On y ajoute un élément sous la forme `(valeur, element)`, avec la fonction `put()`, et on en enlève un élément avec la fonction `get()`, qui renvoie l'élément dont la valeur est la plus faible et le supprime de la file." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from queue import PriorityQueue" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "q = PriorityQueue()\n", "\n", "# put permet de rajouter des éléments\n", "q.put((10, 'a'))\n", "q.put((5, 'b'))\n", "q.put((50, 'c'))\n", "\n", "# get permet de tirer un élément\n", "resultat = q.get()\n", "\n", "print(\"Couple (valeur, élément) :\", resultat)\n", "\n", "\n", "# pour avoir l'élément lui-même, il faut regarder resultat[1]:\n", "print(\"Élément :\", resultat[1])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Ici, même si `b` a été ajouté après `a`, `q.get()` renvoie quand même `b` car la valeur qui y est associée est plus faible." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Algorithe A*\n", "\n", "L'algorithme est très similaire à l'algorithme de parcours en largeur, sauf qu'à la place des sommets visités, on va garder en mémoire la distance entre le sommet de départ et les autres sommets, calculée au fur et à mesure.\n", "\n", "À noter qu'un sommet dont la distance a été calculée est donc un sommet qui a été visité.\n", "\n", "On a donc en mémoire :\n", "* une file de priorité `a_visiter` qui correspond aux éléments que l'on a repérés mais pas encore visités ;\n", "* un dictionnaire `predecesseur` qui indique, pour chaque sommet, quel sommet y a mené dans le parcours (cela va permettre de trouver le plus court chemin) ;\n", "* un dictionnaire `distance`, qui contient, pour chaque sommet, la distance du chemin que l'on a calculé jusqu'à lui pour l'instant.\n", "\n", "Au début, `a_visiter` contient seulement `(0, sommet_de_départ)`, et `distances` est initialisé de façon à ce que pour tous les sommets `s` du graphe, `distance[s] = np.inf`, sauf le sommet de départ qui vaut `distance[sommet_de_départ] = 0`.\n", "\n", "L'algorithme consiste alors à itérer ainsi :\n", "\n", "Tant que `a_visiter` n'est pas vide :\n", "* tirer `s` dans la file de priorité (c'est celui qui est censé être le plus proche de la sortie selon notre heuristique) ;\n", "* si `s` est la sortie (le sommet que l'on cherche à atteindre), renvoyer le chemin qui y mène (grâce à la liste prédecesseurs) ;\n", "* sinon, pour chaque sommet voisin `v` de `s` (donc dans `adj(s)`) :\n", " * si `distance[s] + 1 < distance[v]` (soit on n'a jamais rencontré ce sommet, soit on a trouvé un chemin plus court) :\n", " * mettre à jour `distance[v] = distance[s] + 1` ;\n", " * `predecesseur[v] = s` ;\n", " * ajouter `(distance[v] + heuristique(v, sortie), v)` à `a_visiter`." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "scrolled": true }, "outputs": [], "source": [ "def Astar(G, s, v, afficher=False):\n", " # implémentez l'algorithme A* ici" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# calcul de la solution avec A*\n", "solution = Astar(lab, (0, 0), (19, 9))\n", "\n", "# affichez la solution obtenue \n", "afficher_labyrinthe(lab, solution)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On peut comparer le temps d'exécution sur un labyrinthe assez grand." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import timeit\n", "\n", "grand_lab = labyrinthe((40, 40))\n", "print(timeit.timeit(lambda: plus_court_chemin(grand_lab, (0, 0), (39, 39)), number=1))\n", "print(timeit.timeit(lambda: Astar(grand_lab, (0, 0), (39, 39)), number=1))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** Commenter cette différence de temps d'exécution." ] }, { "cell_type": "markdown", "metadata": {}, "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.8.5" } }, "nbformat": 4, "nbformat_minor": 4 }